class Solution {
public:
    int hIndex(vector<int>& citations) {
        // 下面这种是题解区的优秀解法
        int n = citations.size();
        // 因为 h 不可能超过 n
        // 所以对于引用次数大于 n 的论文，我们在统计的时候，可以看成是引用次数等于 n 的论文。
        vector<int> cnt(n + 1);
        for(int &x : citations)
            cnt[min(x, n)]++;

        // 设 s 为引用次数 ≥i 的论文数，我们需要算出满足 s≥i 的最大的 i
        // 我们可以倒序遍历从 i=n 开始倒序循环，每次循环，把 cnt[i] 加到 s 中
        // 由于我们是倒序循环的，只要 s ≥ i 成立，此时的 i 就是满足 s≥i 的最大的 i
        int s = 0;
        for(int i = n; ; i--)
        {
            s += cnt[i];
            if(s >= i)
                return i;
        }

        // 下面这种是我的解法，需要先排序，时间复杂度是O(N*logN)
        // sort(citations.begin(), citations.end(), greater<int>());
        // int ret = 0, n = citations.size();
        // for(int i = 0; i < n; i++)
        // {
        //     if(citations[i] >= i + 1)
        //         ret++;
        //     else
        //         break;
        // }
        // return ret;
    }
};